﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0038_LengthOfLongestSubstring : IAlgorithm
    {
        // 3. 无重复字符的最长子串

        // 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

        // 提示：
        //  0 <= s.length <= 5 * 10^4
        //  s 由英文字母、数字、符号和空格组成

        public void Test()
        {
            // 算法参数定义
            var s = "wpekpabwwkew";
            // 算法执行与打印
            Console.WriteLine(LengthOfLongestSubstring1(s));
        }

        // 算法
        // map，遍历
        // O(!n)，很拉...
        public int LengthOfLongestSubstring(string s)
        {
            int i = 0, len = 0;
            Dictionary<char, int> his = new Dictionary<char, int>();
            while (i < s.Length)
            {
                if (his.ContainsKey(s[i]))
                {
                    if (len < his.Count)
                        len = his.Count;
                    i = his[s[i]] + 1;
                    his.Clear();
                }
                else
                {
                    his.Add(s[i], i);
                    i++;
                }
            }
            if (len < his.Count)
                len = his.Count;
            return len;
        }

        // 滑动窗口问题
        public int LengthOfLongestSubstring1(string s)
        {
            // 记录字符上一次出现的位置
            // 使用整型数组记录ascii字符出现位置
            int[] last = new int[128];
            for (int i = 0; i < 128; i++)
                last[i] = -1;
            int n = s.Length;
            int res = 0;
            int start = 0; // 窗口开始位置
            for (int i = 0; i < n; i++)
            {
                // ascii字符对应数值
                int index = s[i];
                // 如果重复字符索引+1大于子串起点索引，重新设置子串起点
                if (last[index] + 1 > start)
                    start = last[index] + 1;
                if (i - start + 1 > res)
                    res = i - start + 1;
                last[index] = i;
            }
            return res;
        }
    }
}
